【题解】 士兵占领 网络流 luogu4311 | Qiuly's blog!

【题解】 士兵占领 网络流 luogu4311

Posted on | Edited on | In | Comments:

讨厌死权限题了，然而这题又是 $bzoj$ 的权限题。

$QwQ$ 只好去洛谷上做了，幸好洛谷收的题目比较多。

这题就是网络流，我们先假设棋盘上摆满了士兵，这个时候需要拿走一些士兵，使得棋盘仍然是合法的，求拿走的最多数。

额……最多数让我想起了最大流，不过现在还是先来考虑怎么建图。

我们建两排点，第一排表示行，一共 $M$ 个点，第二排表示列，一共 $N$ 个点。对于一个点 $(x,y)$ ，就像从第一排的第 $x$ 号点向第二排的第 $y$ 号点连一条边权为 $1$ 的边。

这个显然是没有问题的。

然后就是限制，对于第 $k$ 行，至少要有 $L_k$ 个士兵，于是我们从 $s$ 连一条边权为 $L_k$ 的边，连向第一排的第 $k$ 号点。同样的道理，对于第二排的点，我们也像这样连边，连向

$t$ 。

然后就是跑 $dinic$ 了，别忘了跑出来的不是答案，而是最多拿走的士兵数，这个时候用整个棋盘的空位置的个数减去跑出来的 $maxflow$ 才是答案。

需要注意几个点：

  • 当我们在看到了一个行/列的时候，需要判断一下。假设这个是行，那么这行的位置显然有 $n$ 个，如果 $n$ 减去这行障碍的个数，再减去最少要放的士兵数后为负数，那么显然就怎么也不可能有合法的方案，于是直接输出 “JIONG” 就好了。

  • 注意整个棋盘的空位置不是 $N\cdot M$ ，而是 $N\cdot M-K$!

  • 数组大小的话只需要开到 $2n$ ，并不需要开到 $n^2$ ，因为只有两排点。但是边的数组大小需要开到 $n^2$ ，因为我们对于棋盘上的一个点就要连一条边表示它！

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<cmath>
#include<queue>
#include<string>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>

#define A printf("A")
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

const int N=2e2+5;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

std::queue<int> q;
struct Edge{int nxt,to,val;}G[N*N];
int n,m,k,s,t,cnt(1),dep[N],head[N];
int map[N][N],Li[N],Ci[N],Lm[N],Cm[N];

inline void add(int u,int v,int w){
    G[++cnt].nxt=head[u],G[cnt].to=v,G[cnt].val=w,head[u]=cnt;
    G[++cnt].nxt=head[v],G[cnt].to=u,G[cnt].val=0,head[v]=cnt; 
}

inline bool bfs(){
    memset(dep,0,sizeof(dep)); 
    q.push(s);dep[s]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=G[i].nxt){
            int y=G[i].to;
            if(dep[y]||G[i].val<=0)continue;
            dep[y]=dep[x]+1,q.push(y);
        } 
    }return dep[t];
} 
inline int dfs(int x,int flow){
    if(x==t||!flow)return flow;
    int used=0,rlow;
    for(int i=head[x];i;i=G[i].nxt){
        int y=G[i].to;
        if(dep[y]==dep[x]+1&&G[i].val){
            used+=(rlow=dfs(y,min(G[i].val,flow-used)));
            G[i].val-=rlow,G[i^1].val+=rlow;
        }
    }if(!used)dep[x]=-1;
    return used;
}

inline int dinic(){
    int maxflow=0;
    while(bfs())maxflow+=dfs(s,inf);
    return maxflow;
}

int main(){
    IN(m),IN(n),IN(k);
    s=1,t=n+m+1;
    int atot=n*m-k;
    for(int i=1;i<=m;++i)IN(Li[i]);
    for(int i=1;i<=n;++i)IN(Ci[i]);
    for(int i=1;i<=k;++i){
        int x,y;IN(x),IN(y);
        map[x][y]=1,Lm[x]++,Cm[y]++;
    }
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j)
            if(!map[i][j])add(i,j+m,1);
    for(int i=1;i<=m;++i){
        int flow=n-Li[i]-Lm[i];
        if(flow<0){printf("JIONG!");exit(0);}
        else add(s,i,flow);
    }
    for(int i=1;i<=n;++i){
        int flow=m-Ci[i]-Cm[i];
        if(flow<0){printf("JIONG!");exit(0);}
        else add(i+m,t,flow);
    }
    printf("%d\n",atot-dinic());
    return 0;
}

本文标题:【题解】 士兵占领 网络流 luogu4311

文章作者:Qiuly

发布时间:2019年03月01日 - 00:00

最后更新:2019年03月29日 - 13:55

原始链接:http://qiulyblog.github.io/2019/03/01/[题解]luoguP4311/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。